using FineCollection.Intf;


namespace FineCollection.Const
{
    
    /// <summary>
    /// Immutable set. 
    /// All items are different, nulls are not allowed.
    /// </summary>
    /// <typeparam name="T">type of an item.</typeparam>
    public class ConstHashSet<T> : ConstSet<T>, RSet<T>
    {

        #region STATE


        /// <summary>
        /// Maximum count of items when we're using binary search 
        /// instead of hash table.
        /// </summary>
        private const int LimitSimpleCase = 16;


        /// <summary>
        /// Hash codes for each item.
        /// </summary>
        /// <remarks>
        /// Each hash code consists of two parts:
        /// the low "uint" part is the got hash code without sign bit;
        /// the high "uint" part is the division excess by the<see cref="mod"/>. 
        /// </remarks>
        internal readonly uint[] hashKeys;


        /// <summary>
        /// A prime number that used for making a hash table.
        /// </summary>
        internal readonly uint mod;


        /// <summary>
        /// Hash table.
        /// Each cell holds the first index of the <see cref="ConstArray{T}.arr"/>
        /// where the related item can be found,
        /// or <see cref="int.MinValue"/> if no items with such hash key.
        /// The hash table can be null when the number of items is not so big.
        /// </summary>
        internal readonly int[] hashTable;


        #endregion



        #region CONSTRUCTORS


        /// <summary>
        /// Temporary data object for constant fields initialization.
        /// </summary>
        /// <stereotype>transfer object</stereotype>
        private struct ConstructionData
        {
            internal int    firstIndex;
            internal T[]    arr;
            internal int    count;
            internal uint   mod;
            internal uint[] hashKeys;
            internal int[]  hashTable;
        }


        /// <summary>
        /// Constructs a constant hash set.
        /// </summary>
        /// <param name="firstIndex">first index.</param>
        /// <param name="array">array with items to construct set of.</param>
        /// <param name="count">count of items in array.</param>
        /// <param name="removeDuplicates">remove duplicates.</param>
        /// <param name="takeOwnership">take ownership of the given array.</param>
        internal ConstHashSet(int  firstIndex, 
                              T[]  array, 
                              int  count, 
                              bool removeDuplicates, 
                              bool takeOwnership)
            : this(PrepareData(firstIndex, array, count, 
                               removeDuplicates, takeOwnership))
        { }


        private ConstHashSet(ConstructionData cdata)
            : base(cdata.firstIndex, cdata.arr, cdata.count, true)
        {
            this.mod       = cdata.mod;
            this.hashKeys  = cdata.hashKeys;
            this.hashTable = cdata.hashTable;
        }


        private static ConstructionData PrepareData(int firstIndex, 
                                                    T[]  array, 
                                                    int  count, 
                                                    bool removeDuplicates, 
                                                    bool takeOwnership)
        {
            ConstructionData cdata = new ConstructionData
                                         {
                                             firstIndex = firstIndex,
                                             arr = takeOwnership ? array : new T[count],
                                             count = count,
                                             mod = CalculateModeForSize(count),
                                             hashKeys = new uint[count]
                                         };
            if (!takeOwnership)
                System.Array.Copy(array, cdata.arr, count);

            for (int i = 0; i < count; i++)
                cdata.hashKeys[i] = 
                    CalculateHashKeyOf(equator.GetHashCode(cdata.arr[i]), cdata.mod);

            if (cdata.count >= 2)
            {
                System.Array.Sort<uint,T>(cdata.hashKeys, cdata.arr, 0, cdata.count);
                if (removeDuplicates)
                    RemoveDuplicates(cdata.arr, cdata.hashKeys, ref cdata.count);
                    // warning! - the "count" may get wrong value since,
                    //            use  the "cdata.count" instead
            }

            cdata.hashTable = count > LimitSimpleCase 
                                ? MakeHashTable(cdata.hashKeys, cdata.count, cdata.mod) 
                                : null;

            return cdata;
        }


        private static void RemoveDuplicates(T[] arr, uint[] hashKeys, ref int count)
        {
            for (int i = 0; i < count; i++) // count may be changed in this loop
            {
                uint hi = hashKeys[i];
                for (int j = i+1; j < count && hashKeys[j] == hi; )
                {
                    if (equator.Equals(arr[i], arr[j]))
                    {
                        count--;
                        if (j < count)
                        {
                            System.Array.Copy(arr, j + 1, arr, j, count - j);
                            System.Array.Copy(hashKeys, j + 1, hashKeys, j, count - j);
                        }

                        arr[count] = default(T);
                    }
                    else
                    {
                        j++;
                    }
                }
            }
        }


        private static int[] MakeHashTable(uint[] hashKeys, int count, uint mod)
        {
            int[] hashTable = new int[mod];

            for (int h = 0, index = 0; h < mod; h++)
            {
                if (index < count)
                {
                    if (h < hashKeys[index])
                    {
                        hashTable[h] = int.MinValue;
                    }
                    else if (h == hashKeys[index])
                    {
                        hashTable[h] = index;
                        while (index < count && h == hashKeys[index])
                            index++;
                    }
                    else
                    {
                        throw new InternalAlgorythmError(
                            "Internal error when constructing constant hash set: " +
                            "  h=" + h + " but index=" + index + ".");
                    }
                }
                else
                {
                    hashTable[h] = int.MinValue;
                }
            }

            return hashTable;
        }



        private static uint CalculateModeForSize(int n)
        {
            return PrimeNumbers.SelectRingPowerForContainer((uint)n);
        }


        private static uint CalculateHashKeyOf(int givenHashCode, uint mod)
        {
            uint hh = (uint) (givenHashCode & 0x7FFFFFFF);
            uint h = hh % mod;
            return h;
        }



        #endregion



        public override int IndexOf(T item)
        {
            uint h = CalculateHashKeyOf(equator.GetHashCode(item), mod);
            int index = (hashTable != null)
                          ? hashTable[h]
                          : System.Array.BinarySearch(hashKeys, h);

            if (index >= 0)
            {
                do
                {
                    if (equator.Equals(arr[index], item))
                        return firstIndex + index;
                    index++;
                    if (index >= count || hashKeys[index] != h)
                        return int.MinValue;
                } while (true);
            }
            else
            {
                return int.MinValue;
            }
        }



        internal override bool CheckEqualityItemByItem(ConstArray<T> that)
        {
            for (int i = 0; i < count; i++)
                if (!equator.Equals(this.arr[i], that.arr[i]))
                    return false;
            return true;
        }

    }
}